Conventional Password Based Security Systems
Conventional password based security systems typically include two phases. Specifically, during an enrollment phase, users select passwords which are stored on an authentication device such as server. To gain access to resources or data during an authentication phase, the users enter their passwords which are verified against the stored versions of the passwords. If the passwords are stored as plain text, then an adversary who gains access to the system could obtain every password. Thus, even a single successful attack can compromise the security of the entire system.
As shown in FIG. 1, a conventional password based security system 100 stores 115 encrypted 110 passwords 101 in a password database 120 during an enrollment phase 10. As defined herein, the database can be stored in any memory or other computer readable media, tape, flash memory, RAM, ROM, disk, and the like.
Specifically, if X is password 101 to be stored 115, the system 100 actually stores ƒ(X) where ƒ(.) is some encryption or hash function 110. During an authentication phase 20, a user enters a candidate password Y 102, the system determines 130 ƒ(Y), and only grants access 150 to the system when ƒ(Y) matches 140 the stored password ƒ(X), otherwise access is denied 160.
As an advantage, encrypted passwords are useless to an adversary without the encryption functions, which are usually very difficult to invert.
Conventional Biometric Based Security Systems
A conventional biometric security system has the same vulnerability as a password based system which stores unencrypted passwords. Specifically, if the database stores unencrypted biometric parameters, then the parameters are subject to attack and misuse.
For example, in a security system using a face recognition system or voice recognition, an adversary could search for biometric parameters similar to the adversary. After suitable biometric parameters are located, the adversary could modify the parameters to match the appearance or voice of the adversary to gain unauthorized access. Similarly, in a security system using fingerprint or iris recognition, the adversary could construct a device that imitates a matching fingerprint or iris to gain unauthorized access, e.g., the device is a fake finger or fake eye.
It is not always possible to encrypt biometric parameters due to their inherent variability over time. Specifically, biometric parameters X are entered during the enrollment phase. The parameters X are encrypted using an encryption or hashing function ƒ(X), and stored. During the authentication phase, the biometric parameters obtained from the same user can be different. For example, in a security system using face recognition, the user's face can have a different orientation with respect to the camera during enrollment than during authentication. Skin tone, hairstyle and facial features can change. Thus, during authentication, the encrypted biometric parameters will not match with any stored parameters causing rejection.
Error Correcting Codes
An (N, K) error correcting code (ECC)C, over an alphabet Q, includes QK vectors of length N. A linear (N, K) ECC can be described either by using a generator matrix G with N rows and K columns, or by using a parity check matrix H with N-K rows and N columns. The name ‘generator matrix’ is based on the fact that a codeword expressed as a vector w, can be generated from any length K input row vector v by right multiplying the vector v by the matrix G according to w=vG. Similarly, to check if the vector w is a codeword, one can check whether HwT=0, where a column vector wT is a transpose of the row w.
In the standard use of error correcting codes, an input vector v is encoded into the vector w, and either stored or transmitted. If a corrupted version of the vector w is received, a decoder uses redundancy in the code to correct for errors. Intuitively, the error capability of the code depends on the amount of redundancy in the code.
Slepian-Wolf, Wyner-Ziv, and Syndrome Codes
In some sense, a Slepian-Wolf (SW) code is the opposite of an error correcting code. While an error correcting code adds redundancy and expands the data, the SW code removes redundancy and compresses the data. Specifically, vectors x and y represent vectors of correlated data. If an encoder desires to communicate the vector x to a decoder that already has the vector y, then the encoder can compress the data to take into account the fact that the decoder has the vector y.
For an extreme example, if the vectors x and y are different by only one bit, then the encoder can achieve compression by simply describing the vector x, and the location of the difference. Of course, more sophisticated codes are required for more realistic correlation models.
The basic theory of SW coding, as well as the related Wyner-Ziv (WZ) coding, are described by Slepian and Wolf in “Noiseless coding of correlated information sources,” IEEE Transactions on Information Theory, vol. 19, pp. 471-480, Jul. 1973, and Wyner and Ziv in “The rate-distortion function for source coding with side information at the decoder,” IEEE Transactions on Information Theory, vol. 22, pp. 1-10, Jan 1976. More recently, Pradhan and Ramachandran described a practical implementation of such codes in “Distributed Source Coding Using Syndromes (DISCUS): Design and Construction,” IEEE Transactions on Information Theory, vol. 49, pp. 626-643, Mar. 2003.
Essentially, the syndrome codes work by using a parity check matrix H with N-K rows and N columns. To compress a binary vector x of length N to a syndrome vector of length K, determine S=Hx. Decoding often depends on details of the particular syndrome code used. For example, if the syndrome code is trellis based, then various dynamic programming based search algorithms such as the well known Viterbi algorithm can be used to find the mostly likely source sequence x corresponding to the syndrome S and a sequence of side information as described by Pradhan et al.
Alternatively, if low density parity check syndrome codes are used, then belief propagation decoding can be applied as described in “On some new approaches to practical Slepian-Wolf compression inspired by channel coding” by Coleman et al., in Proceedings of the Data Compression Conference, Mar. 2004, pp. 282-291.